
% Criado por P.J.de Rezende antes do Alvorecer da História.
% Modificado em 97-06-15 e 01-02-26 por J.Stolfi.
% modificado em 2003-06-07 21:12:18 por stolfi
% modificado em 2008-10-01 por cll
% \def\lastedit{2010-03-16 17:56:58 by stolfi}

\nonstopmode % PARA RODAR LATEX EM BATCH MODE
\documentclass[11pt,twoside]{article}

\usepackage{techrep-ic}

%%% SE USAR INGLÊS, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A SEGUIR:
\usepackage[brazil]{babel}
%% \usepackage[english]{babel}

%%% SE USAR CODIFICAÇÃO LATIN1 OU UTF-8, ATIVE UM DOS DOIS COMANDOS A
%%% SEGUIR:
%%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

%%% Para obter o tamanho de texto recomendado:
\usepackage[margin=1in]{geometry}

%%% Para simbolos de math
\usepackage{amsmath,amssymb,amsfonts,latexsym}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{color}
\usepackage{multirow}
\usepackage{url}

\definecolor{gray}{gray}{0.95}

\lstset{
  backgroundcolor=\color{gray},
  basicstyle=\ttfamily,
  breaklines=true,
  captionpos=b,
  columns=fixed,
  language=sh,
  showstringspaces=false,
  tabsize=2
}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Número do relatório
\TRNumber{02}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{13} % Dois dígitos
\TRMonth{05} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{R.A.Q. Cruz \and S.G. Fadel \and F.A. Neto}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{Solucionador paralelo de sistemas lineares em GPU}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% O que segue é apenas uma sugestão - sinta-se à vontade para
% usar seu formato predileto, desde que as margens tenham pelo
% menos 25mm nos quatro lados, e o tamanho do fonte seja pelo menos
% 11pt. Certifique-se também de que o título e lista de autores
% estão reproduzidos na íntegra na página 1, a primeira depois da
% página de capa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{Cruz, Fadel e Neto}{Solucionador paralelo de sistemas lineares em
GPU}
\pagestyle{myheadings}
\thispagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TÍTULO e NOMES DOS AUTORES, completos, para a página 1.
% Use "\\" para quebrar linhas, "\and" para separar autores.
%
\title{Solucionador paralelo de sistemas lineares em GPU}

\author{Rommel Anatoli Quintanilla Cruz \and Samuel Gomes Fadel \and Filipe
Alves Neto}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}

Soluções eficientes para sistemas de equações lineares são cruciais em diversas
áreas do conhecimento. Para estes problemas, as unidades de processamento
gráfico se destacam por possuírem uma vasta quantidade de processadores
paralelos especializados. Este trabalho é parte da disciplina de Programação
Concorrente do ICMC/USP com o objetivo de avaliar uma solução paralela para esta
tarefa. Concluiu-se que neste caso uma boa abordagem de comunicação entre os
processos é essencial para a eficiência da solução.

\end{abstract}

\section{Introdução}
Por possuírem aplicações em muitas áreas do conhecimento, sistemas de equações
lineares se mostram muito importantes para modelar e resolver vários tipos de
problemas. Entretanto, a alta complexidade dos algoritmos existentes para
resolvê-los pode limitar a quantidade de variáveis que podem ser utilizadas para
modelar estes problemas, prejudicando a obtenção de uma boa solução.

Por outro lado, as unidades de processamento gráfico (\emph{graphics processing
units} -- GPUs) ganharam mais espaço na computação de alto desempenho
principalmente por conterem, em pouco espaço, uma vasta quantidade de
processadores paralelos especializados. Originalmente projetados para operações
gráficas, estes processadores recentemente vem sendo utilizados para resolver
problemas altamente paralelizáveis, principalmente pela complexidade reduzida na
intercomunicação e na eficiência energética, quando comparados a sistemas de
multiprocessadores.

Neste trabalho, implementou-se o algoritmo Jacobi-Richardson para resolver
sistemas lineares em versões sequenciais e versões paralelas utilizando GPU.
Este trabalho foi desenvolvido como parte do curso SC0143 -- Programação
Concorrente do Instituto de Ciências Matemáticas e de Computação (ICMC) da
Universidade de São Paulo (USP).

\section{Objetivos}
O objetivo deste trabalho é projetar e aplicar algoritmos paralelos
implementados em CUDA e OpenCL para resolver sistemas lineares com base no
algoritmo Jacobi-Richardson. Além disso, objetiva-se comparar os tempos de
execução destes algoritmos com versões sequenciais.

\section{Implementação}
Na implementação da solução, inicialmente pensou-se em paralelizar as operações
em cada iteração do algoritmo Jacobi-Richardson, cada \emph{thread} calcularia
apenas um $x[i]$. Entretanto, esta solução não obteve melhorias no tempo de
execução.

A solução adotada se utiliza da ideia inicial juntamente com um fato
interessante que pode ser utilizado no algoritmo Jacobi-Richardson: ao
utilizarmos os $x[i]$ calculados na iteração atual para calcular os outros
$x[j]$ restantes da mesma iteração, não é necessário armazenar o vetor com os
anteriores e os atuais. Com isso, reduz-se tanto o acesso quanto a quantidade de
informações na memória global. Para fins de comparação de desempenho, foram
implementadas versões sequenciais tanto com o algoritmo clássico quanto com esta
otimização.

Nesta solução, as \emph{threads} compartilham entre si apenas a informação sobre
o maior erro obtido na iteração atual entre cada uma. Assim, quando o maior erro
for menor do que o erro estipulado ou o número de iterações máximo for atingido,
a execução termina. Além disso, ao fim de cada iteração, ocorre uma chamada à
função \texttt{\_\_syncthreads()} (\texttt{barrier()}, no caso da implementação
em OpenCL) a fim de sincronizar as \emph{threads} para evitar divisão por zero
no cálculo do erro.

O código-fonte dos programas estão hospedados no repositório digital do Google
Code no endereço \url{https://code.google.com/p/pc2013-grupo06-turmab/} na
pasta \texttt{projeto}.

\subsection{Decomposição do problema}
Nas soluções paralelas, utilizou-se decomposição de dados híbrida, pois cada
\emph{thread} é responsável pelo cálculo de cada $x[i]$ (decomposição
recursiva), mas dependem dos dados gerados pelas outras \emph{threads}
(decomposição de dados). Na Figura~\ref{fig:Decomp}, está ilustrada a
organização das \emph{threads} de acordo com os blocos e \emph{grids}.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/decomp.eps}
    \caption{
        Diagrama ilustrando a decomposição do problema. Os \emph{grids} e blocos
        são ambos unidimensionais e cada thread é responsável por uma variável
        do sistema linear.
    }
    \label{fig:Decomp}
\end{figure}

Entretanto, para realmente obter os maiores ganhos de desempenho, foi necessário
explorar diferentes formas de organizar as \emph{threads} em \emph{grids} e
blocos. Na seção seguinte, serão apresentados os resultados com as quatro
abordagens exploradas nas versões CUDA:

\begin{itemize}
    \item Maximizando o número de \emph{threads} por bloco e usando uma
        quantidade de blocos suficiente para atingir um número de \emph{threads}
        maior ou igual ao número de variáveis do problema;
    \item Minimizando o número de \emph{threads} por bloco e usando uma
        quantidade de blocos suficiente para atingir um número de \emph{threads}
        maior ou igual ao número de variáveis do problema;
    \item Utilizar mais \emph{threads} do que blocos e utilizando um número de
        \emph{threads} e blocos múltiplos do tamanho de
        \emph{warp}\footnote{Número mínimo de \emph{threads} que a GPU consegue
        utilizar para acesso coalescente à memória da GPU.} da GPU (chamado
        ``Baseado em Warp'');
    \item Balancear o número de \emph{threads} e blocos, utilizando múltiplos do
        tamanho de \emph{warp} da GPU (chamado ``Baseado em Warp (2)'').
\end{itemize}

Na versão OpenCL, as \emph{threads} são divididas igualmente para cada
\emph{stream processor}.

\section{Resultados}

O \emph{hardware} utilizado para os experimentos foram os seguintes:
\begin{itemize}
    \item As duas versões sequenciais foram rodadas em um processador Intel Core i7 2600 (3.4 GHz).
    \item A versão em GPU CUDA foi rodada em uma placa de vídeo modelo GeForce GTX 460.
    \item A versão OpenCL foi rodada em uma placa de vídeo modelo Radeon Mobility HD 7690M XT.
\end{itemize}

Nesta seção são apresentados os resultados de desempenho da solução proposta. Os
dados são mostrados com um intervalo de confiança de 95\% e cada teste foi
executado 10 vezes. Nas Figuras~\ref{fig:Tempos}, \ref{fig:TemposSeq1} e
\ref{fig:TemposSeq2} estão os tempos totais de execução. Na
Figura~\ref{fig:Tempos} estão apenas os tempos dos algoritmos paralelos em CUDA
e OpenCL; nas Figuras~\ref{fig:TemposSeq1} e \ref{fig:TemposSeq2} estão os
tempos de execução juntamente com a versão sequencial sem e com a otimização do
algoritmo de Jacobi-Richardson, respectivamente. Nas Figuras~\ref{fig:Speedup1}
e \ref{fig:Speedup2} estão os \emph{speedups} dos algoritmos implementados em
CUDA e OpenCL em relação ao algoritmo sequencial sem e com a otimização,
respectivamente.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.85\linewidth]{img/tempos.eps}
    \caption{
        Tempos de execução das diferentes abordagens de divisão em blocos e
        \emph{grids}.
    }
    \label{fig:Tempos}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.85\linewidth]{img/tempos_seq1.eps}
    \caption{
        Tempos de execução das diferentes abordagens de divisão em blocos e
        \emph{grids}, comparados ao tempo de execução da versão sequencial
        original.
    }
    \label{fig:TemposSeq1}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.85\linewidth]{img/tempos_seq2.eps}
    \caption{
        Tempos de execução das diferentes abordagens de divisão em blocos e
        \emph{grids}, comparados ao tempo de execução da versão sequencial
        otimizada.
    }
    \label{fig:TemposSeq2}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.85\linewidth]{img/speedup1.eps}
    \caption{\emph{Speedup} em relação à versão sequencial original.}
    \label{fig:Speedup1}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.85\linewidth]{img/speedup2.eps}
    \caption{
        \emph{Speedup} em relação à versão sequencial do algoritmo otimizado.
    }
    \label{fig:Speedup2}
\end{figure}

Todas as soluções paralelas propostas obtiveram melhores resultados para
matrizes de ordem maior ou igual a 1000 quando comparadas às soluções
sequenciais, conforme observado nas Figuras~\ref{fig:TemposSeq1}
e~\ref{fig:TemposSeq2}.

Entre as soluções paralelas, observando a Figura~\ref{fig:Tempos}, percebe-se
que as versões CUDA baseadas em warp foram as mais estáveis, enquanto as demais
apresentaram diferentes comportamentos dependendo da ordem do problema.

Por fim, para as versões paralelas mais estáveis, percebe-se que quanto maior a
ordem do problema, melhor é o speedup em relação à versão sequencial, conforme
observado nas Figuras~\ref{fig:Speedup1} e~\ref{fig:Speedup2}. Para um sistema
linear de ordem 4000, por exemplo, o \emph{speedup} da versão CUDA baseada em
\emph{warp} em relação a versão sequencial otimizada foi maior que 200.

\section{Conclusões}

As soluções baseadas em GPU dependem fortemente do mapeamento das
\emph{threads}. Para a solução adotada neste trabalho, o melhor mapeamento
consistiu em basear o número de \emph{threads} e blocos em múltiplos do tamanho
de \emph{warp}, favorecendo o número de \emph{threads}. Esta divisão, porém,
pode não ser eficaz para outros modelos de GPU.

Além disso, características deste paradigma de programação, como pouca memória
compartilhada entre \emph{threads} do mesmo bloco, falta de recursos de
comunicação interblocos e instruções limitadas de comunicação intrablocos,
dificultam a implementação dos algoritmos de forma paralela.

Apesar destas limitações, obteve-se ótimos resultados ao paralelizar o método
Jacobi-Richardson para solução de sistemas lineares. Em sua solução paralela, há
pouca comunicação entre as \emph{threads}, superando tais limitações. Nota-se
que a solução atingiu os melhores \emph{speedups} em relação ao algoritmo
sequencial para sistemas de ordem superiores. Em contrapartida, os resultados
demonstrados na Figura~\ref{fig:Speedup2} indicam que a solução pode não ser
escalável para sistemas ainda maiores.

\bibliographystyle{abnt}
\bibliography{relatorio}

\end{document}
